package  main.java.leetcode.editor.cn;
//2023-03-11 16:44:55
//输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。 
//
// 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 12
//输出：5
// 
//
// 示例 2： 
//
// 
//输入：n = 13
//输出：6 
//
// 
//
// 限制： 
//
// 
// 1 <= n < 2^31 
// 
//
// 注意：本题与主站 233 题相同：https://leetcode-cn.com/problems/number-of-digit-one/ 
// Related Topics 递归 数学 动态规划 👍 407 👎 0

class OneNzhengShuZhong1chuXianDeCiShuLcof {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new OneNzhengShuZhong1chuXianDeCiShuLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int countDigitOne(int n) {
        long mulk = 1;
        int ans = 0;

        for(int k = 0;mulk<=n;k++){
            ans += (n/(mulk*10))*mulk+Math.min(Math.max(n%(mulk *10)-mulk+1,0),mulk);
            mulk = mulk*10;
        }

        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
